package ljl.codetop;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

public class _76_minwindow {

    /**
     * 滑出来了，但是很慢，200 多毫秒
     */
    static class tryout {
        public String minWindow(String s, String t) {
            Map<Character, Integer> dic = new HashMap<>();
            for (char c : t.toCharArray()) {
                dic.put(c, dic.getOrDefault(c, 0) + 1);
            }
            Map<Character, Integer> cur = new HashMap<>();
            int l = -1, r = s.length(), len = Integer.MAX_VALUE;
            LinkedList<Integer> q = new LinkedList<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                q.add(i);
                cur.put(c, cur.getOrDefault(c, 0) + 1);
                while (!q.isEmpty()) {
                    if (containsAll(cur, dic)) {
                        int from = q.peek();
                        if (i - from + 1 < len) {
                            l = from;
                            r = i + 1;
                            len = i - from + 1;
                        }
                        c = s.charAt(q.poll());
                        if (cur.get(c) == 1) cur.remove(c);
                        else cur.put(c, cur.get(c) - 1);
                    } else break;
                }
            }
            return l == -1 ? "" : s.substring(l, r);
        }
        boolean containsAll(Map<Character, Integer> cur, Map<Character, Integer> target) {
            for (Character c : target.keySet()) {
                if (!cur.containsKey(c)) return false;
                if (cur.get(c) < target.get(c)) return false;
            }
            return true;
        }
    }

    /**
     * 逼友的解法
     */
    static class friend_b {
        public String minWindow(String s, String t) {
            if (s == null || s.length() == 0 || t == null || t.length() == 0){
                return "";
            }
            int[] need = new int[128];
            for (int i = 0; i < t.length(); i++) {
                need[t.charAt(i)]++;
            }
            int l = 0, r = 0, size = Integer.MAX_VALUE;
            int count = t.length();
            int start = 0;
            while (r < s.length()) {
                char c = s.charAt(r);
                if (need[c] > 0) {
                    count--;
                }
                need[c]--;
                if (count == 0) {
                    while (l < r && need[s.charAt(l)] < 0) {
                        need[s.charAt(l)]++;
                        l++;
                    }
                    if (r - l + 1 < size) {
                        start = l;
                        size = r - l + 1;
                    }
                    need[s.charAt(l)]++;
                    l++;
                    count++;
                }
                r++;
            }
            return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
        }
    }

    static class copy_friend_b {
        public String minWindow(String s, String t) {
            int[] required = new int[128];
            for (char c : t.toCharArray()) {
                required[c]++;
            }
            int count = t.length();
            int start = -1;
            int l = 0, i = 0, size = Integer.MAX_VALUE;
            while (i < s.length()) {
                char c = s.charAt(i);
                if (required[c] > 0) count--;
                required[c]--;
                if (count == 0) {
                    while (l < i && required[s.charAt(l)] < 0) {
                        required[s.charAt(l)]++;
                        l++;
                    }
                    if (i - l + 1 < size) {
                        start = l;
                        size = i - l + 1;
                    }
                    required[s.charAt(l)]++;
                    count++;
                    l++;
                }
                i++;
            }
            return start == -1 ? "" : s.substring(start, start + size);
        }
    }

    /**
     * 跟我的大差不差吧，就是没用队列，我用队列确实有点脱裤子放屁之嫌
     */
    static class off1 {

        public String minWindow(String s, String t) {
            Map<Character, Integer> ori = new HashMap<>();
            Map<Character, Integer> cnt = new HashMap<>();
            for (char c : t.toCharArray()) {
                ori.put(c, ori.getOrDefault(c, 0) + 1);
            }
            int l = 0, r = 0;
            int len = Integer.MAX_VALUE, ansL = -1, ansR = 0;
            int sLen = s.length();
            while (r < sLen) {
                if (ori.containsKey(s.charAt(r))) {
                    cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (check(ori, cnt) && l <= r) {
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        ansL = l;
                        ansR = r + 1;
                    }
                    if (ori.containsKey(s.charAt(l))) {
                        cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
                ++r;
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }
        public boolean check(Map<Character, Integer> ori, Map<Character, Integer> cnt) {
            for (Map.Entry<Character, Integer> e: ori.entrySet()) {
                if (cnt.getOrDefault(e.getKey(), 0) < e.getValue()) {
                    return false;
                }
            }
            return true;
        }
    }

    static class copy_off1 {
        public String minWindow(String s, String t) {
            Map<Character, Integer> small = new HashMap<>();
            for (char c : t.toCharArray()) {
                small.put(c, small.getOrDefault(c, 0) + 1);
            }
            Map<Character, Integer> big = new HashMap<>();
            int l = 0, i = 0, len = s.length();
            int resL = -1, size = Integer.MAX_VALUE;
            while (i < len) {
                char c = s.charAt(i);
                if (small.containsKey(c))
                    big.put(c, big.getOrDefault(c, 0) + 1);
                while (contains(big, small)) {
                    if (i - l + 1 < size) {
                        resL = l;
                        size = i - l + 1;
                    }
                    c = s.charAt(l);
                    if (small.containsKey(c))
                        big.put(c, big.get(c) - 1);
                    l++;
                }
                i++;
            }
            return size == Integer.MAX_VALUE ? "" : s.substring(resL, resL + size);
        }

        /**
         * 这不用 getOrDefault 而是 contains || get，会导致慢 1/3，150ms -> 205ms
         */
        boolean contains(Map<Character, Integer> big, Map<Character, Integer> small) {
            for (Map.Entry<Character, Integer> entry : small.entrySet()) {
                if (big.getOrDefault(entry.getKey(), 0) < entry.getValue())
                    return false;
            }
            return true;
        }
    }
}
